iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 5
1
自我挑戰組

30天找回寫程式手感計劃!!!系列 第 5

Day5 - 第幾個 100 天還是很有感覺之久違的寫程式由簡單數學題目切入吧!( 3/3 )

  • 分享至 

  • xImage
  •  

各位觀眾、各位大大們~~~~~
這個挑戰終於來到 5日目 了~~~~~
今天廢話不多說,
讓我們馬上進入正題!
(對了,先預告個,沒意外的話今天應該是數學系列的最後一篇了,
後面應該會開始進入網頁前端的複習(排版))

正片開始

今日素材:完全數

會挑這個題目也是因為我記得這好像是某年 C 語言的期中考題XD
介紹就有請維基大師~~~~~

https://zh.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E6%95%B0
完全數(Perfect number),又稱完美數或完備數,是一些特殊的自然數:
它所有的真因子(即除了自身以外的因數)的和,恰好等於它本身
完全數不可能是楔形數、平方數、佩爾數或費波那契數。
例如:第一個完全數是6,它有因數1、2、3、6,除去它本身6外,其餘3個數相加,1+2+3 = 6,恰好等於本身。
第二個完全數是28,它有因數1、2、4、7、14、28,除去它本身28外,其餘5個數相加,1+2+4+7+14 = 28,也恰好等於本身。後面的數是496、8128。

相信看完以上說明大家就知道完全數是啥咪了吧~
事不宜遲,讓我們快來動手吧:D

本日挑戰 Start

  1. 先用 6 寫完全數判斷的邏輯
let basicNum = 6;
let factorSum = 0; // 因數相加結果
for ( let i=1; i<basicNum; i++ ){
    if ( basicNum%i === 0 ){
        factorSum += i; // 可以整除表示為因數,把因數加起來
    }
}

if ( factorSum === factorSum ){
    console.log(`${basicNum} 為完全數!`);
}

https://ithelp.ithome.com.tw/upload/images/20200911/20129873qzNTjAIAEB.png
看起來第 1 步成功了,就可以繼續往下走了:D
(但也許有眼尖的人發現以上這段程式有很大的問題XDDDD
這邊先不破梗,就讓我繼續陳述挑戰過程吧XD)

  1. 改成 28 驗證看看
let basicNum = 28;
let factorSum = 0; // 因數相加結果
for ( let i=1; i<basicNum; i++ ){
    if ( basicNum%i === 0 ){
        factorSum += i; // 可以整除表示為因數,把因數加起來
    }
}

if ( factorSum === factorSum ){
    console.log(`${basicNum} 為完全數!`);
}

https://ithelp.ithome.com.tw/upload/images/20200911/20129873DyTKb2OqoB.png

  1. 改成 14 看看
let basicNum = 14;
let factorSum = 0; // 因數相加結果
for ( let i=1; i<basicNum; i++ ){
    if ( basicNum%i === 0 ){
        factorSum += i; // 可以整除表示為因數,把因數加起來
    }
}

if ( factorSum === factorSum ){
    console.log(`${basicNum} 為完全數!`);
} else{
    console.log(`${basicNum} 不是完全數!`);
}

https://ithelp.ithome.com.tw/upload/images/20200911/20129873dhD9l6hK7i.png
What?! 14 怎麼可能是完全數!!!!!

  1. 還好我並沒有花太多時間就看到不對的地方了......
    我眼殘= = factorSum === factorSum 當然會 true 啊.....
let basicNum = 14;
let factorSum = 0; // 因數相加結果
for ( let i=1; i<basicNum; i++ ){
    if ( basicNum%i === 0 ){
        factorSum += i; // 可以整除表示為因數,把因數加起來
    }
}

if ( basicNum === factorSum ){
    console.log(`${basicNum} 為完全數!`);
} else{
    console.log(`${basicNum} 不是完全數!`);
}

https://ithelp.ithome.com.tw/upload/images/20200911/20129873Psm6cU6miN.png
很好,終於正常了,呼......

  1. 本關不難,tune一下程式,減少計算次數
    寫程式不能只是追求結果正確,
    程式效率一樣重要,

    一個程式要計算 10000 次才能得到結果,
    但一個只要計算 100 次就能得到一樣的結果,
    馬上就立判高下了吧XD
    而且 performance 絕對是去任何地方都會追求的目標,
    因為一個 performance 不好的程式那問題可大可小,
    小的話頂多只是程式跑不出來,大的話可能會影響整個系統癱瘓之類的......
    咳......這又是另外一個故事了,有機會再講XD
    先讓我們回到本日正題~
    當然我知道我現在寫法還不成熟,
    但就讓我先用我目前的步調慢慢 tune 程式吧~

- 1 一定是任何數的因數,所以factorSum設為1,迴圈改由2開始計算

let basicNum = 28;
let factorSum = 1;
for ( let i=2; i<basicNum; i++ ){ // 這邊改由 2 開始
    if ( basicNum%i === 0 ){
        factorSum += i;
    }
}

if ( basicNum === factorSum ){
    console.log(`${basicNum} 為完全數!`);
} else{
    console.log(`${basicNum} 不是完全數!`);
}

- 因數是成對的,當你找到 1 個,其實另外 1 個就知道了,就不用傻傻的繼續算。
這個概念就是,
要找因數每次都會從 2 開始找,
例如 28 我就會從 2,3,4..... 找到 27,
但不覺得哪裡怪怪的嗎?
28 因數有:1,2,4,7,14,28,
因數是成對的
第 1 個被找到的因數是 2,28/2 = 14,2 跟 14 成對,
當你找到 2,表示你其實就已經找到 14 了,
直接把因數相加 2+14 並且把迴圈終點直接改成 14,
就不用傻傻算到完。

為了讓大家知道差異,
在程式我有埋一個計算次數的變數 countTimes,
就讓我們先看先前未改的時候 28 需要幾次計算吧~
[原邏輯]
https://ithelp.ithome.com.tw/upload/images/20200911/20129873FHef0EN8qv.png
[新邏輯(改成會動態修改迴圈終點)]

let basicNum = 28; // 要拿來驗證是否為完全數的數字
let factorSum = 1; // 因數相加
let countTimes = 0; // 計算次數

let endNum = basicNum;
for ( let i=2; i<endNum; i++ ){
    if ( basicNum%i === 0 ){
        factorSum += i; // 先加上最初找到的因數
        factorSum += basicNum/i; // 再加上該因數相對的因數
        endNum = basicNum/i; // 將終點動態改成該因數相對的因數
    }
    countTimes++;
}

if ( basicNum === factorSum ){
    console.log(`${basicNum} 為完全數!`);
} else{
    console.log(`${basicNum} 不是完全數!`);
}

console.log(`本次計算次數為 ${countTimes} 次`);

https://ithelp.ithome.com.tw/upload/images/20200911/20129873JA6uoSb16F.png
計算次數從 26 次降成 5 次就能算出來!!!!!
但你會說這樣有很厲害嗎?
隨著要計算的數字越大,
需要驗證的因數範圍也會隨之變大,
那個差距是很可觀的。
如果前面不先 tune,
後面你就發現即使數字沒有很大還是會操到網頁跑不出來.......

  1. 再拿 496 驗證一下到目前寫的邏輯對不對吧~
let basicNum = 496; // 要拿來驗證是否為完全數的數字
let factorSum = 1; // 因數相加
let countTimes = 0; // 計算次數

let endNum = basicNum;
for ( let i=2; i<endNum; i++ ){
    if ( basicNum%i === 0 ){
        factorSum += i;
        factorSum += basicNum/i;
        endNum = basicNum/i;
    }
    countTimes++;
}

if ( basicNum === factorSum ){
    console.log(`${basicNum} 為完全數!`);
} else{
    console.log(`${basicNum} 不是完全數!`);
}

console.log(`本次計算次數為 ${countTimes} 次`);

https://ithelp.ithome.com.tw/upload/images/20200911/20129873IMZziLcf4W.png

  1. 當然只有用單一數字驗證是否為完全數很無聊吧XD
    試著找出 2 ~ 1000 有幾個完全數吧!
let perfectArray = [];
// let basicNum = 496; // 要拿來驗證是否為完全數的數字
let factorSum = 1; // 因數相加
let countTimes = 0; // 計算次數

for ( let basicNum=2; basicNum<1000; basicNum++ ){
    let endNum = basicNum;
    for ( let i=2; i<endNum; i++ ){
        if ( basicNum%i === 0 ){
            factorSum += i;
            factorSum += basicNum/i;
            endNum = basicNum/i;
        }
        countTimes++;
    }
    if ( basicNum === factorSum ){
        console.log(`${basicNum} 為完全數!`);
        perfectArray.push(basicNum);
    }
    factorSum = 1; // 一次計算完就要將因數相加設成初始值 1
}

console.log(`本次計算次數為 ${countTimes} 次`);

https://ithelp.ithome.com.tw/upload/images/20200911/2012987381Y7t91p4l.png

  1. 但你會不會不是想要從一個範圍內找出完全數,
    而是想要找出前 4 個完全數有哪些呢?
    讓我們試著改改看吧~
let perfectArray = [];
// let basicNum = 496; // 要拿來驗證是否為完全數的數字
let factorSum = 1; // 因數相加
let countTimes = 0; // 計算次數

// 直到找到 4 個完全數才停止迴圈計算
for ( let basicNum=2; perfectArray.length<4 ; basicNum++ ){
    let endNum = basicNum;
    for ( let i=2; i<endNum; i++ ){
        if ( basicNum%i === 0 ){
            factorSum += i;
            factorSum += basicNum/i;
            endNum = basicNum/i;
        }
        countTimes++;
    }
    if ( basicNum === factorSum ){
        console.log(`${basicNum} 為完全數!`);
        perfectArray.push(basicNum);
    }
    if ( perfectArray.length == 4 ){
        break; // 當已經找到第 4 個完全數,任務也完成了,就跳出迴圈不要再計算了
    }
    factorSum = 1;
}

https://ithelp.ithome.com.tw/upload/images/20200911/20129873ZFN8qZ6R34.png
本日任務打完收工~~~~~~

[後記]

之所以為什麼是找出 4 個不是 5 個呢?
因為~~~ 跑到第 5 個網頁就轉圈圈了orz
可以看到跑到第 4 個,計算次數就來到 10246704 次了orz
所以我想這個程式還有很大空間可以 tune,
有機會想要再 tune tune 看!
(但我不想用維基說的數學家已知規律去找,因為我想以未知情況去探索的邏輯來寫,
直接套已知規律就失去程式練功的意義了)
https://ithelp.ithome.com.tw/upload/images/20200911/2012987333W5lwz1L2.png
也許有路過的大大們可以給小的建議,
也很歡迎跟小的講,
也許就可以變成隔天文章了呢~
好的,今日節目到這告一段落,
讓我們明天再見吧~~~~~~:D
https://ithelp.ithome.com.tw/upload/images/20200911/20129873aZMijUk1pP.jpg


上一篇
Day4 - 第幾個 100 天還是很有感覺之久違的寫程式由簡單數學題目切入吧!( 2/3 )
下一篇
Day6 - 令人敬佩的數字~佩服數 ( Admirable Numbers )
系列文
30天找回寫程式手感計劃!!!36
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言